#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>

#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>

using namespace std;

int* move(int* a,int* b,int max,int len,int print=0){
	assert(a!=NULL && b!=NULL && max>0 && len>0);
	int* ee=(int*)malloc(len*sizeof(int));
	memset(ee,-1,len*sizeof(int));
	if(len==1){
		if(b[0]==-1){
			ee[0]=a[0];
		}else{
			ee[0]=max-a[0];
		}
		return ee;
	}
	
	int ex=0;
	int i=0,j;
	while(ex!=len){
		i++;
		for(j=0;j<len;j++){
			if(ee[j]>0)
				continue;
			a[j]+=b[j];
			if(a[j]==0 || a[j]==max){
				ex++;
				if(print){
					for(int m=0;m<len;m++){
						printf("%d[%d] ",a[m],b[m]);
					}
					printf(" at %d seconds exit\n",i);
				}
				ee[j]=i;
			}else if(j==0){
				if(a[j]==a[j+1]){
					b[j]*=-1;
					b[j+1]*=-1;
				}
			}else if(j==len-1){
				if(a[j]==a[j-1]){
					b[j]*=-1;
					b[j-1]*=-1;
				}
			}else{
				if(a[j]==a[j+1]){
					b[j]*=-1;
					b[j+1]*=-1;
				}else if(a[j]==a[j-1]){
					b[j]*=-1;
					b[j-1]*=-1;
				}
			}
		}
	}
	return ee;
}

void generate(vector< vector<int> >& result,vector<int>* cur,int next,int len){
	assert(len>0 && cur!=NULL);
	if(len==1){
		cur->push_back(next);
		result.push_back(*cur);
//		cur->push_back(0); //push_back a 0 for pop
/*		vector<int>* n=new vector<int>(len);
		copy(cur.begin(),cur.end(),n);
*/		
		return;
	}
	cur->push_back(next);
	generate(result,cur,1,len-1);
	cur->pop_back();
	generate(result,cur,-1,len-1);
	cur->pop_back();
}

int main(){
	int a[]={3,7,11,17,23};
	int b[]={1,-1,1,1,-1};
	
	int c[]={5};
	int d[]={1};
	int f[]={-1};
	
	vector< vector<int> > result;
	vector<int>* cur=new vector<int>;
	generate(result,cur,1,5);
	cur=new vector<int>;
	generate(result,cur,-1,5);
	
	
	vector< vector<int> >::const_iterator it=result.begin();
	int min=100,max=-1;
	int* maxa, *mina, *maxb ,* minb;
	for(;it!=result.end();it++){
		//copy((*it).begin(),(*it).end(),ostream_iterator<int>(cout," "));
		//cout<<"\n";
		int* para=(int*)malloc(5*sizeof(int));
		int* st=(int*)malloc(5*sizeof(int));
		vector<int> n=*it;
		for(int i=0;i<n.size();i++){
			para[i]=n[i];
			st[i]=n[i];
		}
		int* xx=(int*)malloc(5*sizeof(int));
		for(int x=0;x<5;x++)
			xx[x]=a[x];
		
		int* ex=move(xx,para,27,5);
		for(int i=0;i<5;i++){
			if(ex[i]<min){
				min=ex[i];
				mina=a;
				minb=st;
			}
			else if(ex[i]>max){
				max=ex[i];
				maxa=a;
				maxb=st;
			}
		}
	}
	
	cout<<" total: "<<result.size()<<endl;
	cout<<" max: "<<max<<"  min:"<<min<<endl;
	
	cout<<"max at:\n";
	for(int i=0;i<5;i++){
		cout<<maxa[i]<<"["<<maxb[i]<<"]"<<" ";
	}
	cout<<"\n";

	cout<<"min at:\n";
	for(int i=0;i<5;i++){
		cout<<mina[i]<<"["<<minb[i]<<"]"<<" ";
	}
	cout<<"\n";
	
	int* e=move(c,d,15,1);
	assert(e[0]==10);
	e=move(c,f,15,1);
	assert(e[0]==5);
	
	e=move(a,b,27,5);
}